/***尚硅谷Java数据结构与java算法                   ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***冒泡排序                    P55          ***/
/***C++ 实现版本    written by Daniel           ***/
#include <iostream>
//用于获取系统时间
#include <ctime>
//用于生成随机数
#include <cstdlib>
using std::cout;
using std::endl;
#define MAX 80000

void printArr(int *arr, int size)
{
    for(int i=0;i<size;i++)
    {
        std::cout<<arr[i]<<"\t";
    }
    std::cout<<std::endl;
}

void bubbleSort(int *arr, int size)
{
    //i代表进行第几次 大循环
    int temp=0;
    //通过一个标志位来优化排序算法
    bool flag=false;
    //如果在某次排序过程中，没有发生元素移动，说明排序完成，退出循环
    for(int i=0;i<size;i++){
        //j代表 大循环到达的下标
        flag=false;
        for(int j=0;j<(size-i-1);j++){
            if (arr[j]>arr[j+1]){
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
                flag=true;
            }
        }
        if (flag==false){
            break;
        }
        // printArr(arr,5);
    }
}

int main(int argc, char **argv)
{
    //使用系统时间生成一个随机数种子
    srand(time(NULL));    
    int *array=new int[MAX];
    for(int i=0;i<MAX;i++){
        array[i]=rand()%MAX;
        //cout<<array[i]<<endl;
    }
    time_t now=time(NULL);
    std::cout<<"now="<<now<<std::endl;
    bubbleSort(array,MAX);
    //printArr(array,MAX);
    time_t newNow=time(NULL);
    std::cout<<"newNow="<<newNow<<std::endl;
    std::cout<<"一共花了"<<newNow-now<<"秒";
    delete[] array;
    return 0;
}